package sit.engreal.leetcode.problems100;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combinations/">77. 组合</a>
 */
public class LeetCode77 {
    public List<List<Integer>> combine(int n, int k) {
        final List<List<Integer>> permutations = new ArrayList<>();
        dfs(permutations, new ArrayList<>(k), 1, n, k);
        return permutations;
    }


    private void dfs(final List<List<Integer>> permutations, List<Integer> selects, int m, int n, int k) {
        if (selects.size() == k) {
            final ArrayList<Integer> permutation = new ArrayList<>(selects.size());
            permutation.addAll(selects);
            permutations.add(permutation);
            return;
        }
        if (k - selects.size() > n - m + 1) {
            return;
        }
        for (int i = m; i <= n; i++) {
            selects.add(i);
            dfs(permutations, selects, i + 1, n, k);
            selects.remove(selects.size() - 1);
        }
    }

    public static void main(String[] args) {
        final LeetCode77 demo = new LeetCode77();


        demo.combine(1, 1).forEach(System.out::println);

        demo.combine(4, 2).forEach(System.out::println);
    }

}
